//给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
// 
//
// 如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
//输出："apple"
// 
//
// 示例 2： 
//
// 
//输入：s = "abpcplea", dictionary = ["a","b","c"]
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// 1 <= dictionary.length <= 1000 
// 1 <= dictionary[i].length <= 1000 
// s 和 dictionary[i] 仅由小写英文字母组成 
// 
// Related Topics 数组 双指针 字符串 排序 
// 👍 266 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LongestWordInDictionaryThroughDeleting {
    public static void main(String[] args) {
        String s = "abpcplea";
        List<String> list = new ArrayList<>();
        list.add("ale");
        list.add("apple");
        list.add("monkey");
        list.add("plea");
        list.add("abpcplaaa");
        list.add("abpcllllll");
        list.add("abccclllpppeeaaaa");
        new LongestWordInDictionaryThroughDeleting().new Solution().findLongestWord(s, list);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 倒是解答成功了，就是耗时比较长
         * 在比较两个字符串时确实用到了双指针
         * 整个思路就是遍历所有的word，然后根据s进行进行双指针遍历比较
         * 遍历时做根据p2进行判断，匹配上的话p2++
         * 遍历结束后如果标记不为false且word的指针遍历完了，说明匹配上了
         * 更新结果就行了，如果匹配到的word的长度和s一样长了，说明完全匹配了
         *
         */
        public String findLongestWord(String s, List<String> dictionary) {
            String res = "";
            for (String word : dictionary){
                if (word.length()>s.length()) continue;
                int p1 =0;
                int p2 =0;
                while (p1<s.length()&&p2<word.length()){
                    if (s.charAt(p1)==word.charAt(p2)) p2++;
                    p1++;
                }
                if (p2==word.length()){
                    if (word.length() == s.length()) return word;
                    if (res.length()<word.length()) res = word;
                    else if (res.length()==word.length()&&word.compareTo(res)<0) res = word;
                }
            }
            return res;
        }

        /**
         * 题解当中的一个优化：先对dictionary进行排序，1.优先级为长度 2.字典升序
         * 这样排序完只用找到第一个匹配到的就行(word长度>s的直接跳过)
         * 而且在匹配时不用额外的标记位了，直接根据p2进行判断
         * 匹配的到p2++，这样最终只需要判断p2与word长度是否相等
         */
        public String findLongestWord2(String s, List<String> list) {
            Collections.sort(list, (a,b)->{
                if (a.length() != b.length()) return b.length() - a.length();
                return a.compareTo(b);
            });
            int n = s.length();
            for (String ss : list) {
                int m = ss.length();
                int i = 0, j = 0;
                while (i < n && j < m) {
                    if (s.charAt(i) == ss.charAt(j)) j++;
                    i++;
                }
                if (j == m) return ss;
            }
            return "";
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}